%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template

\usepackage{sectsty} % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps

\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{UCAS, SCCE} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 生物特征识别 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国 201618013229046} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title

%----------------------------------------------------------------------------------------
%	PROBLEM 1
%----------------------------------------------------------------------------------------

\section{graph embedding}

\begin{enumerate}
    \item 图嵌入算法描述
    \begin{enumerate}
        \item 问题定义：数据  $ X= [ x_1, x_2, x_3, \ldots, x_n ] , x_i \in \mathcal{R}^D$，$G$为数据$X$所形成的图，对应的权重矩阵为$W$，对角阵$D$，拉普拉斯矩阵$L$
        \item 目标：求一个映射$f:X\to Y, Y=[y_1,y_2,y_3,\ldots,y_n],y_i \in \mathcal{R}_d$，使得$Y$是$X$的最优低维表示，这里的最优指的是\textbf{最好的刻画了数据对之间的相似性}
        \item 形式化描述
        \begin{align*}
          obj & \indent & \arg\min_Y \sum_{i\ne j}\| y_i-y_j \|^2 W_{ij} \\
          s.t.& \indent & Y^T B Y = c
        \end{align*}
        化简可得
        \begin{align*}
        obj & \indent & \arg\min_Y Y^T L Y \\
        s.t.& \indent & Y^T B Y = c
        \end{align*}
    \end{enumerate}
  \item 图嵌入算法的线性化
    若指定映射为线性，即有$Y=X^T a$，则问题可进一步化简为：
    \begin{align*}
      obj & \indent &  \arg\min_{a} a^T X L X^T a\\
      s.t.& \indent & a^T a = d
    \end{align*}
    由拉格朗日乘子法可得：$XLX^Ta = \lambda a$，是一个广义特征值问题。
\end{enumerate}

\section{PCA}
\begin{enumerate}
  \item PCA的思想：最小化重构误差，也就是知道到方差最大的方向，可形式化描述为如下优化问题：
  \begin{align*}
    obj & \indent &  \arg\max_{a} a^T C a\\
    s.t.& \indent & \|a\| = 1
  \end{align*}
  其中$C$为样本的协方差矩阵。
  \item PCA与Graph Embedding的关系：对比图嵌入算法和PCA的形式化描述，可知当$XLX^T$与$C$产生联系时，两者便可以产生联系。
  这里直接给出结果，中间过程见参考文献[1].
  \[\text{定义样本的权重矩阵为:}W_{ij}=\frac{1}{n}\to XLX^T=C,\text{则图嵌入算法的最优化形式便和PCA相同。}\]
\end{enumerate}
\section{LDA}
\begin{enumerate}
  \item LDA算法描述：样本$X$中有两类，类均值分别为$m_1,m_2$,求使得投影后低维数据最具鉴别性的线性投影。
  \item 形式化描述：
  \begin{align*}
    obj & \indent & \arg\max \frac{a^T S_b a}{a^T S_t a} \\
    \text{or} &\\
    obj & \indent & \arg\max{a^T S_b a}\\
    s.t.& \indent & a^T S_t a = C
  \end{align*}
  拉格朗日求解可得：$S_b a = \lambda S_t a$，是一个广义特征值求解问题。
  \item LDA与Graph Embedding之间的关系
  若令$W_1,W_2$分别为$n_1 \times n_1, n_2 \times n_2$的矩阵，$W_1$的元素全为$\frac{1}{n_1}$，$W_2$的元素全为$\frac{1}{n_2}$，那么有
  \[
    S_b=\sum_{i=1}^{2}n_i m_i m_i^T = XWX^T
  \]
  其中假设数据已经去中心化，且
  \[
  W=\left(
  \begin{array}{cc}
    W_1 & 0 \\
    0   & W_2
  \end{array}
  \right)
  \]
  \end{enumerate}
  \section{LPP(Locality Preserving Projections)}
\begin{enumerate}
  \item 基本概念：局部保持投影是一种线性的拉普拉斯映射。
  \item 形式化描述：
  \begin{align*}
    obj & \indent& \arg\min_a a^T XLX^T a\\
    s.t.& \indent& a^T X D X^T a=1
  \end{align*}
  \item relation of LPP and graph embedding
  \[ B=D \]
\end{enumerate}
\section{spectral clustering}
\begin{enumerate}
  \item 基本思想：将数据进行拉普拉斯线性映射到低维空间，然后使用k-means进行聚类。
  \item 形式化描述：
  \begin{align*}
    obj& \indent & \arg\min y^TLy \\
    s.t.& \indent & y^Ty=1
  \end{align*}
  得到的$y$的即为$L$的前$k$个最小的特征值所对应的特征向量。
  \item relation to graph embedding
  \[ B=I \]

\end{enumerate}

\section{reference}
\begin{enumerate}
\item Shuicheng Yan, Dong Xu, Benyu Zhang and Hong-Jiang Zhang. Graph Embedding and Extensions: A General Framework
   for Dimensionality Reduction . PAMI. Vol:29, No:1, Jan 2017 \\
 \item 陈江峰。线性图嵌入算法及其应用。 北京：北京交通大学博士学位论文。Sep 2011.

\end{enumerate}


\end{document}
